W9. Вероятностный анализ и рандомизированные алгоритмы

Автор

Nikolai Kudasov

Дата публикации

18 марта 2026 г.

1. Краткое содержание

1.1 Основы теории вероятностей
1.1.1 Пространство элементарных исходов и события

Чтобы строго рассуждать о случайности, нужен формальный язык. Исходная точка — пространство элементарных исходов (sample space) \(S\): множество всех возможных исходов эксперимента. Например, при трёх подбрасываниях монеты каждая последовательность из орла (H) и решки (T) длины три — возможный исход:

\[S = \{HHH, HHT, HTH, HTT, THH, THT, TTH, TTT\}\]

Событие (event) — любое подмножество пространства исходов. Например, событие «ровно одна решка» соответствует:

\[P_1 = \{HHT, HTH, THH\}\]

Такая формализация позволяет аккуратно описывать, что может произойти и с какой вероятностью.

1.1.2 Аксиомы вероятности

Распределение вероятностей (probability distribution) — это функция \(\text{Pr} : \mathcal{P}(S) \rightarrow \mathbb{R}\) (где \(\mathcal{P}(S)\) — множество всех подмножеств \(S\)), сопоставляющая каждому событию вещественное число и удовлетворяющая четырём аксиомам:

  1. \(\text{Pr}\{A\} \geq 0\) для любого события \(A\) — вероятности неотрицательны.
  2. \(\text{Pr}\{S\} = 1\) — вероятность того, что произойдёт какой-то исход, равна 1.
  3. \(\text{Pr}\{A \cup B\} = \text{Pr}\{A\} + \text{Pr}\{B\}\) для любых несовместных событий \(A\) и \(B\) (то есть \(A \cap B = \emptyset\)).
  4. \(\text{Pr}\left\{\bigcup_i A_i\right\} = \sum_i \text{Pr}\{A_i\}\) для любой конечной или счётной последовательности попарно несовместных событий.

\(\text{Pr}\{A\}\) называют вероятностью (probability) события \(A\).

1.1.3 Базовые свойства вероятности

Следующие свойства выводятся непосредственно из аксиом:

  1. \(\text{Pr}\{\emptyset\} = 0\)

    Доказательство: \(\emptyset \cap S = \emptyset\), поэтому \(\text{Pr}\{\emptyset \cup S\} = \text{Pr}\{\emptyset\} + \text{Pr}\{S\}\). Так как \(\emptyset \cup S = S\), получаем \(\text{Pr}\{S\} = \text{Pr}\{\emptyset\} + \text{Pr}\{S\}\), откуда \(\text{Pr}\{\emptyset\} = 0\).

  2. \(\text{Pr}\{\overline{A}\} = 1 - \text{Pr}\{A\}\), где \(\overline{A} = S \setminus A\) — дополнение к \(A\).

    Доказательство: \(A \cap \overline{A} = \emptyset\) и \(A \cup \overline{A} = S\), поэтому \(\text{Pr}\{A\} + \text{Pr}\{\overline{A}\} = \text{Pr}\{S\} = 1\).

  3. \(\text{Pr}\{A \cup B\} = \text{Pr}\{A\} + \text{Pr}\{B\} - \text{Pr}\{A \cap B\} \leq \text{Pr}\{A\} + \text{Pr}\{B\}\)

    Доказательство: Разобьём \(B\) на непересекающиеся части \(A \cap B\) и \(B \setminus (A \cap B)\). Тогда \(A \cup B = A \cup (B \setminus (A \cap B))\), откуда \(\text{Pr}\{A \cup B\} = \text{Pr}\{A\} + \text{Pr}\{B\} - \text{Pr}\{A \cap B\}\).

Пример (подбрасывание монеты): честная монета подбрасывается 3 раза. Если все 8 исходов равновероятны, каждый имеет вероятность \(\frac{1}{8}\). У события \(P_1 = \{HHT, HTH, THH\}\) вероятность \(\text{Pr}\{P_1\} = \frac{3}{8}\).

1.2 Дискретные распределения вероятностей

Распределение называется дискретным (discrete), если оно задано на конечном или счётном пространстве исходов.

Особый случай — равномерное распределение (uniform distribution): если \(S\) конечно и каждый исход \(s \in S\) имеет вероятность \(\text{Pr}\{s\} = \frac{1}{|S|}\), распределение равномерно. Говорят: «выбираем элемент \(S\) равномерно наугад (uniformly at random)».

Примеры:

  • Честный шестигранный кубик: \(S = \{1, 2, 3, 4, 5, 6\}\), каждый исход с вероятностью \(\frac{1}{6}\). Это равномерное распределение.
  • Сумма двух честных кубиков: сумма от 2 до 12, но не все суммы равновероятны (например, 7 чаще, чем 2). Это не равномерное распределение.
  • Случайный студенческий ID в группе из \(n\) студентов: равномерное (каждый ID равновероятен).
1.3 Дискретные случайные величины

Дискретная случайная величина (discrete random variable) \(X\) — функция \(X : S \rightarrow \mathbb{R}\), сопоставляющая каждому исходу вещественное число. Например, \(X\) может быть счётом в игре или числом орлов в серии подбрасываний.

Определяют: \[\text{Pr}\{X = x\} = \sum_{s \in S : X(s) = x} \text{Pr}\{s\}\]

Функцию \(f(x) = \text{Pr}\{X = x\}\) называют функцией вероятности (probability mass function, PMF) величины \(X\).

1.3.1 Математическое ожидание

Математическое ожидание (expected value), также expectation или mean случайной величины \(X\) — вероятностно взвешенное среднее:

\[E[X] = \sum_x x \cdot \text{Pr}\{X = x\}\]

Ожидание показывает, каким был бы «средний» исход при многократном повторении эксперимента. Например, если за орёл начисляется 1 очко, за решку — 0, то для честной монеты ожидание \(\frac{1}{2}\): в среднем пол-очка за бросок.

Пример: в игре с двумя монетами: \(+6\) за HH, \(+1\) за HT или TH и \(-4\) за TT:

\[E[X] = 6 \cdot \frac{1}{4} + 1 \cdot \frac{1}{2} + (-4) \cdot \frac{1}{4} = \frac{6}{4} + \frac{2}{4} - \frac{4}{4} = 1\]

1.3.2 Линейность математического ожидания

Ожидание — линейный оператор (linear operator):

\[E[X + Y] = E[X] + E[Y]\] \[E[\alpha X] = \alpha E[X] \text{ для любой константы } \alpha\]

Это верно для любых случайных величин \(X\) и \(Y\), не только независимых. Linearity of expectation — самое используемое свойство в вероятностном анализе: сложную величину можно разбить на индикаторы.

Если \(X\) — случайная величина, а \(g\) — произвольная функция, то \(g(X)\) тоже случайная величина и: \[E[g(X)] = \sum_x g(x) \cdot \text{Pr}\{X = x\}\]

Вообще говоря, \(E[g(X)] \neq g(E[X])\) — например, \(E[X^2] \neq (E[X])^2\), если \(X\) не константа.

Когда \(E[X]\) не существует? Ожидание задаётся суммой \(\sum_x x \cdot \text{Pr}\{X = x\}\). Сумма может расходиться — тогда говорят, что ожидания в обычном конечном смысле нет. Классический пример — парадокс Санкт-Петербурга (St. Petersburg paradox): честная монета бросается до первого орла, выигрыш \(2^k\), если орёл впервые на броске \(k\). Ожидаемый выигрыш \(\sum_{k=1}^{\infty} 2^k \cdot \frac{1}{2^k} = \infty\) — ожидание бесконечно. В анализе алгоритмов обычно рассматривают конечные «хорошие» распределения, и эта тонкость не мешает.

1.3.3 Независимые случайные величины

Случайные величины \(X\) и \(Y\) независимы (independent), если значение одной не даёт информации о другой. Формально: \(X\) и \(Y\) независимы тогда и только тогда, когда

\[\text{Pr}\{X = x \text{ and } Y = y\} = \text{Pr}\{X = x\} \cdot \text{Pr}\{Y = y\}\]

для всех \(x\) и \(y\).

Пример зависимых величин: \(S = \{H, T\}\) (один бросок). Пусть \(X(H) = 1, X(T) = 0\) и \(Y(H) = 0, Y(T) = 1\). Тогда \(\text{Pr}\{X = 1 \text{ and } Y = 1\} = 0\), но \(\text{Pr}\{X = 1\} \cdot \text{Pr}\{Y = 1\} = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4} \neq 0\). Значит \(X\) и \(Y\) зависимы: из \(X = 1\) (орёл) следует \(Y = 0\).

Правило произведения для независимых величин: если \(X\) и \(Y\) независимы, то \[E[XY] = E[X] \cdot E[Y]\]

Это сильнее аддитивности и верно только при независимости.

1.4 Индикаторные случайные величины

Индикаторная случайная величина (indicator random variable), также Bernoulli random variable для события \(A\):

\[I\{A\} = \begin{cases} 1 & \text{if event } A \text{ occurs,} \\ 0 & \text{if event } A \text{ does not occur.} \end{cases}\]

Индикаторы переводят вероятностные утверждения в вычисления ожиданий. Ключевая лемма:

Лемма (Cormen et al. 2022, Lemma 5.1). Пусть \(X_A = I\{A\}\). Тогда \(E[X_A] = \text{Pr}\{A\}\).

Доказательство: \[E[X_A] = 1 \cdot \text{Pr}\{A\} + 0 \cdot \text{Pr}\{\overline{A}\} = \text{Pr}\{A\} \quad \square\]

Зачем индикаторы? Они разлагают сложные величины в суммы простых. Если \(X = X_1 + X_2 + \cdots + X_n\), где \(X_i = I\{A_i\}\), то по линейности:

\[E[X] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n \text{Pr}\{A_i\}\]

Это проще, чем напрямую анализировать распределение \(X\).

Пример (ожидаемое число орлов): \(n\) бросков честной монеты, \(X_i = I\{\text{the } i\text{-th toss is heads}\}\), \(X = \sum_{i=1}^n X_i\). Тогда:

\[E[X] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n \frac{1}{2} = \frac{n}{2}\]

1.5 Вероятностный анализ

Вероятностный анализ (probabilistic analysis) изучает поведение алгоритма (часто время работы) средствами теории вероятностей. Вместо вопроса «каково худшее время?» спрашивают: «каково ожидаемое (expected) время при усреднении по входам?»

Нужны:

  1. Известное или предполагаемое распределение (distribution) входов.
  2. Обоснованные предположения, что оно реалистично.
  3. Вычисление ожидаемого времени работы (expected running time) по этому распределению.

Если разумное распределение входов обосновать нельзя, вероятностный анализ может быть неприменим.

1.5.1 Задача о найме (hiring problem)

Представьте найм AI-агента. Есть \(n\) кандидатов, оценка по очереди стоит \(c_c\), найм (замена текущего агента) стоит \(c_h > c_c\).

HIRE-ASSISTANT(n)
1  best = 0         // candidate 0 is a least-qualified dummy
2  for i = 1 to n
3      interview candidate i      // cost c_c
4      if candidate i is better than candidate best
5          best = i
6          hire candidate i       // cost c_h

Худший случай: кандидаты приходят по неубыванию качества — нанимаем каждого. Стоимость наймов: \(c_h n\).

Лучший случай: лучший кандидат первый — один найм. Стоимость: \(c_h\).

Вероятностный анализ: порядок кандидатов — равномерно случайная перестановка (все \(n!\) порядков равновероятны). Пусть \(X_i = I\{\text{the } i\text{-th candidate is hired}\}\). \(i\)-й кандидат нанимается тогда и только тогда, когда он лучший среди первых \(i\). При случайном порядке любой из первых \(i\) равновероятно лучший, поэтому:

\[\text{Pr}\{\text{the } i\text{-th candidate is hired}\} = \frac{1}{i}\]

Ожидаемое число наймов:

\[E[X] = E\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n \frac{1}{i} = \Theta(\log n)\]

здесь \(\sum_{i=1}^n \frac{1}{i} = H_n\) — \(n\)-е гармоническое число (harmonic number), рост \(\Theta(\log n)\). В среднем дорогих наймов \(\Theta(\log n)\), хотя всех \(n\) кандидатов мы просматриваем.

1.6 Рандомизированные алгоритмы

Вероятностный анализ выше предполагал случайный вход. А если порядок фиксирован (возможно, враждебный)? Рандомизированный алгоритм (randomized algorithm) берёт случайность под контроль: вместо надежды на случайный вход алгоритм создаёт случайность.

Определение: алгоритм рандомизирован, если его поведение зависит не только от входа, но и от случайных решений во время выполнения (значения random-number generator).

Рандомизированный найм: перед HIRE-ASSISTANT случайно перемешать кандидатов:

RANDOMLY-PERMUTE(A, n)
1  for i = 1 to n
2      swap A[i] with A[RANDOM(i, n)]

Получается равновероятная перестановка. Тогда независимо от исходного порядка ожидаемое число наймов — \(\Theta(\log n)\), даже против противника, выбравшего худший порядок.

Идея: вероятностный анализ опирается на случайность входа; рандомизированные алгоритмы — на случайность самого алгоритма.

1.7 Рандомизированный quicksort

Quicksort — классический divide-and-conquer алгоритм сортировки:

  1. Разделяй и властвуй (divide-and-conquer).
  2. В среднем \(\Theta(n \log n)\), в худшем случае \(\Theta(n^2)\).
  3. Устойчив (stable) (порядок равных элементов сохраняется).
  4. Эффективная in-place реализация (без дополнительного массива).

Идея:

  • Divide: разбиение массива относительно опорного элемента (pivot) — меньшие слева, большие справа.
  • Conquer: подмассив из одного элемента уже отсортирован.
  • Combine: соединить отсортированные части с pivot посередине.

Худший случай, например, уже отсортированный массив и выбор первого/последнего элемента как pivot.

Случайный выбор pivot снимает предсказуемость худшего случая:

RANDOMIZED-PARTITION(A, p, r)
1  i = RANDOM(p, r)
2  exchange A[r] with A[i]
3  return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r)
1  if p < r
2      q = RANDOMIZED-PARTITION(A, p, r)
3      RANDOMIZED-QUICKSORT(A, p, q - 1)
4      RANDOMIZED-QUICKSORT(A, q + 1, r)
1.7.1 Анализ рандомизированного quicksort

Лемма (Cormen et al. 2022, Lemma 7.1). Если \(X\) — общее число сравнений в PARTITION за всё выполнение, то время QUICKSORT есть \(O(n + X)\).

Пусть \(z_1 < z_2 < \cdots < z_n\) — элементы в отсортированном порядке. Определим:

\[X_{ij} = I\{z_i \text{ is compared with } z_j\}\]

Тогда \(X = \sum_{i=1}^n \sum_{j=i+1}^n X_{ij}\).

Ключевое наблюдение: \(z_i\) и \(z_j\) сравниваются тогда и только тогда, когда один из них — первый выбранный pivot из множества \(Z_{ij} = \{z_i, z_{i+1}, \ldots, z_j\}\).

Так как каждый из \(j - i + 1\) элементов \(Z_{ij}\) равновероятно первый pivot из этого множества:

\[\text{Pr}\{z_i \text{ is compared with } z_j\} = \frac{2}{j - i + 1}\]

Ожидаемое число сравнений:

\[E[X] = \sum_{i=1}^n \sum_{j=i+1}^n \frac{2}{j-i+1} = \sum_{i=1}^n \sum_{k=1}^{n-i} \frac{2}{k+1} < \sum_{i=1}^n \sum_{k=1}^{n-i} \frac{2}{k} = \sum_{i=1}^n O(\log n) = O(n \log n)\]

Итог по randomized quicksort:

  • Как обычный quicksort, но pivot случайный.
  • Ожидаемое время: \(\Theta(n \log n)\) на любом входе.
  • Худшее время по-прежнему \(\Theta(n^2)\), но оно зависит от ГСЧ, а не от входа — противник не может «подобрать» вход под худший случай.
1.8 Вероятностный анализ bucket sort

Bucket sort — сортировка за линейное время при предположении: значения входа равномерно распределены на интервале (часто \([0, 1)\)).

Алгоритм:

  1. Разбить \([0, 1)\) на \(n\) равных по длине\(^*\) подинтервалов («ведра», buckets). При равномерном входе вероятность попасть в каждое ведро одинакова.
  2. Элемент \(a\) кладём в ведро \(\lfloor na \rfloor\).
  3. Каждое ведро сортируем insertion sort.
  4. Конкатенируем отсортированные ведра.

\(^*\)«Равные» здесь — в смысле вероятности: каждое из \(n\) ведёр покрывает интервал длины \(\frac{1}{n}\), и при равномерном распределении каждый элемент независимо попадает в данное ведро с вероятностью \(\frac{1}{n}\).

Почему быстро? В среднем в каждом ведре \(\frac{n}{n} = 1\) элемент, insertion sort внутри ведра — \(O(1)\) в среднем.

1.8.1 Формальный анализ

Пусть \(n_i\) — число элементов в ведре \(i\). Время bucket sort:

\[T(n) = \Theta(n) + \sum_{i=0}^{n-1} O(n_i^2)\]

Нужно \(E\left[\sum_{i=0}^{n-1} O(n_i^2)\right] = \sum_{i=0}^{n-1} O(E[n_i^2])\).

Пусть \(X_{ij} = I\{A[j] \text{ falls into bucket } i\}\), тогда \(n_i = \sum_{j=1}^n X_{ij}\).

Вычисление \(E[n_i^2]\):

\[E[n_i^2] = E\left[\left(\sum_{j=1}^n X_{ij}\right)^2\right] = E\left[\sum_{j=1}^n X_{ij}^2 + \sum_{j \neq k} X_{ij} X_{ik}\right] = \sum_{j=1}^n E[X_{ij}^2] + \sum_{j \neq k} E[X_{ij} X_{ik}]\]

Первая сумма: \(X_{ij} \in \{0,1\}\), значит \(X_{ij}^2 = X_{ij}\): \[E[X_{ij}^2] = 1^2 \cdot \frac{1}{n} + 0^2 \cdot \left(1 - \frac{1}{n}\right) = \frac{1}{n}\]

Вторая сумма: при \(j \neq k\) события независимы (независимые равномерные элементы), по правилу произведения: \[E[X_{ij} X_{ik}] = E[X_{ij}] \cdot E[X_{ik}] = \frac{1}{n^2}\]

Первых слагаемых \(n\), вторых \(n(n-1)\):

\[E[n_i^2] = n \cdot \frac{1}{n} + n(n-1) \cdot \frac{1}{n^2} = 1 + \frac{n-1}{n} = 2 - \frac{1}{n}\]

Ожидаемое время:

\[E[T(n)] = \Theta(n) + n \cdot O\!\left(2 - \frac{1}{n}\right) = \Theta(n)\]

1.9 Случайно построенные бинарные деревья поиска

Бинарное дерево поиска (binary search tree, BST) удовлетворяет BST property: для каждой вершины \(x\) все ключи в левом поддереве \(\leq x.\text{key}\), в правом \(\geq x.\text{key}\).

Форма BST целиком определяется порядком вставки ключей. Если ключи вставляются в равномерно случайном порядке, дерево называют randomly built BST.

1.9.1 Два разных понятия «случайного BST»
  1. Randomly chosen BST: равновероятно выбирается одна из всех допустимых форм BST на \(n\) вершинах. Число форм — \(n\)-е число Каталана (Catalan number) \(C_n = \frac{1}{n+1}\binom{2n}{n}\).
  2. Randomly built BST: пустое дерево, затем вставляется равномерно случайная перестановка \(n\) различных ключей. Все \(n!\) перестановок равновероятны, но разные перестановки могут давать одну форму — это не равномерное распределение по формам.

Для \(n = 5\): 42 формы (\(C_5 = 42\)) и \(5! = 120\) перестановок. «Высокие» перекошенные формы вероятнее при случайных вставках, чем при случайном выборе формы.

Ожидаемая высота randomly built BST: известно (Cormen et al. 2022, §12.4), ожидаемая высота \(\Theta(\log n)\) — как у почти сбалансированного дерева.

2. Определения

  • Sample space (\(S\)): множество всех исходов случайного эксперимента.
  • Event: подмножество пространства исходов \(S\).
  • Probability distribution: функция \(\text{Pr} : \mathcal{P}(S) \rightarrow \mathbb{R}\), удовлетворяющая четырём аксиомам вероятности.
  • Discrete probability distribution: распределение на конечном или счётном пространстве исходов.
  • Uniform distribution: на конечном \(S\) каждый исход с вероятностью \(\frac{1}{|S|}\).
  • Discrete random variable: функция \(X : S \rightarrow \mathbb{R}\) на конечном или счётном пространстве исходов.
  • Probability mass function: \(f(x) = \text{Pr}\{X = x\}\) для дискретной величины \(X\).
  • Expected value (\(E[X]\)): \(E[X] = \sum_x x \cdot \text{Pr}\{X = x\}\).
  • Linearity of expectation: \(E[X + Y] = E[X] + E[Y]\) для любых величин (независимость не нужна).
  • Independent random variables: \(\text{Pr}\{X = x \text{ and } Y = y\} = \text{Pr}\{X = x\} \cdot \text{Pr}\{Y = y\}\) для всех \(x, y\).
  • Indicator random variable (\(I\{A\}\)): 1 при событии \(A\), иначе 0; \(E[I\{A\}] = \text{Pr}\{A\}\).
  • Probabilistic analysis: анализ работы алгоритма через вероятность, обычно expected running time по распределению входов.
  • Expected running time: среднее время по входам (или по случайным битам) с весами вероятностей.
  • Randomized algorithm: поведение зависит от входа и от random-number generator.
  • Random permutation: перестановка, равновероятная среди всех \(n!\); строится, например, RANDOMLY-PERMUTE.
  • Binary search tree (BST): бинарное дерево с BST property.
  • Randomly built BST: вставка \(n\) ключей в случайном порядке; ожидаемая высота \(\Theta(\log n)\).
  • Catalan number: \(C_n = \frac{1}{n+1}\binom{2n}{n}\) — число форм бинарного дерева на \(n\) узлах.
  • Pivot (quicksort): опорный элемент разбиения; в randomized quicksort — равновероятный в текущем подмассиве.
  • Bucket sort: распределение по \(n\) ведрам, insertion sort внутри ведёр, конкатенация; при равномерном входе на \([0,1)\) ожидаемое время \(\Theta(n)\).

3. Формулы

  • Вероятность дополнения: \(\text{Pr}\{\overline{A}\} = 1 - \text{Pr}\{A\}\)
  • Включение–исключение (два события): \(\text{Pr}\{A \cup B\} = \text{Pr}\{A\} + \text{Pr}\{B\} - \text{Pr}\{A \cap B\}\)
  • Expected value: \(E[X] = \displaystyle\sum_x x \cdot \text{Pr}\{X = x\}\)
  • Linearity of expectation: \(E[X + Y] = E[X] + E[Y]\) и \(E[\alpha X] = \alpha E[X]\)
  • Функция от случайной величины: \(E[g(X)] = \displaystyle\sum_x g(x) \cdot \text{Pr}\{X = x\}\)
  • Независимость (произведение): если \(X\) и \(Y\) независимы, \(E[XY] = E[X] \cdot E[Y]\)
  • Лемма об индикаторе: \(E[I\{A\}] = \text{Pr}\{A\}\)
  • Ожидаемое число наймов (hiring problem): \(E[\text{hires}] = \displaystyle\sum_{i=1}^n \frac{1}{i} = H_n = \Theta(\log n)\)
  • Вероятность сравнения (quicksort): \(\text{Pr}\{z_i \text{ compared with } z_j\} = \dfrac{2}{j - i + 1}\)
  • Ожидаемое число сравнений (quicksort): \(E[X] = O(n \log n)\)
  • Ожидаемое \(n_i^2\) в bucket sort: \(E[n_i^2] = 2 - \dfrac{1}{n}\)
  • Число Каталана: \(C_n = \dfrac{1}{n+1}\dbinom{2n}{n}\)
  • Гармоническое число: \(H_n = \displaystyle\sum_{i=1}^n \frac{1}{i} = \Theta(\log n)\)

4. Примеры и задания

4.1. Доказать или опровергнуть тождества вероятности (Набор задач 7, Задание 1)

Для каждого равенства либо докажите его из аксиом вероятности и тождеств для множеств, либо приведите контрпример:

(a) \(\text{Pr}\{A \setminus B\} = \text{Pr}\{A\} - \text{Pr}\{B\}\)

(b) \(\text{Pr}\{A \cup (B \cap C)\} = \text{Pr}\{(A \cap B) \cup C\}\)

Нажмите, чтобы увидеть решение

(a) \(\text{Pr}\{A \setminus B\} = \text{Pr}\{A\} - \text{Pr}\{B\}\):

В общем случае неверно. Приведём контрпример.

Пусть \(S = \{1, 2, 3\}\) с равномерным распределением (\(\text{Pr}\{s\} = \frac{1}{3}\) для каждого \(s\)). Пусть \(A = \{1, 2\}\) и \(B = \{2, 3\}\).

Тогда:

  • \(\text{Pr}\{A \setminus B\} = \text{Pr}\{\{1\}\} = \frac{1}{3}\)
  • \(\text{Pr}\{A\} - \text{Pr}\{B\} = \frac{2}{3} - \frac{2}{3} = 0\)

Так как \(\frac{1}{3} \neq 0\), равенство не выполняется.

Верная формула: \(\text{Pr}\{A \setminus B\} = \text{Pr}\{A\} - \text{Pr}\{A \cap B\}\), она следует из \(A = (A \setminus B) \cup (A \cap B)\) при непересекающихся частях.

(b) \(\text{Pr}\{A \cup (B \cap C)\} = \text{Pr}\{(A \cap B) \cup C\}\):

В общем случае неверно. Контрпример.

Пусть \(S = \{1, 2, 3, 4\}\) с равномерным распределением. Пусть \(A = \{1\}\), \(B = \{2\}\), \(C = \{3\}\).

  • \(B \cap C = \{2\} \cap \{3\} = \emptyset\), значит \(A \cup (B \cap C) = \{1\}\), поэтому \(\text{Pr}\{A \cup (B \cap C)\} = \frac{1}{4}\).
  • \(A \cap B = \{1\} \cap \{2\} = \emptyset\), значит \((A \cap B) \cup C = \{3\}\), поэтому \(\text{Pr}\{(A \cap B) \cup C\} = \frac{1}{4}\).

Здесь совпало случайно. Попробуем \(A = \{1, 2\}\), \(B = \{2, 3\}\), \(C = \{3, 4\}\):

  • \(B \cap C = \{3\}\), значит \(A \cup (B \cap C) = \{1, 2, 3\}\): \(\text{Pr} = \frac{3}{4}\).
  • \(A \cap B = \{2\}\), значит \((A \cap B) \cup C = \{2, 3, 4\}\): \(\text{Pr} = \frac{3}{4}\).

Снова равно. Попробуем \(A = \{1\}\), \(B = \emptyset\), \(C = \{2, 3, 4\}\):

  • \(B \cap C = \emptyset\), значит \(A \cup (B \cap C) = \{1\}\): \(\text{Pr} = \frac{1}{4}\).
  • \(A \cap B = \emptyset\), значит \((A \cap B) \cup C = \{2, 3, 4\}\): \(\text{Pr} = \frac{3}{4}\).

Так как \(\frac{1}{4} \neq \frac{3}{4}\), равенство не выполняется.

Ответ: (a) Неверно — контрпример выше. (b) Неверно — контрпример с \(A = \{1\}\), \(B = \emptyset\), \(C = \{2,3,4\}\) на равномерном пространстве из 4 исходов.

4.2. Доказать или опровергнуть тождества для ожиданий (Набор задач 7, Задание 2)

Для каждого пункта докажите или приведите контрпример. Все случайные величины вещественные, все ожидания существуют.

(a) \(E\!\left[\dfrac{X + Y + Z}{3}\right] = \dfrac{E[X] + E[Y] + E[Z]}{3}\)

(b) \(E[\sqrt{XY}] = \sqrt{E[X]\,E[Y]}\) при независимых \(X\) и \(Y\).

(c) \(E[\max(X, Y)] = \max(E[X], E[Y])\)

(d) \(E[X^3] = (E[X])^3\)

Нажмите, чтобы увидеть решение

(a) \(E\!\left[\dfrac{X + Y + Z}{3}\right] = \dfrac{E[X] + E[Y] + E[Z]}{3}\):

Верно. По linearity of expectation: \[E\!\left[\frac{X + Y + Z}{3}\right] = \frac{1}{3} E[X + Y + Z] = \frac{1}{3}(E[X] + E[Y] + E[Z]) = \frac{E[X] + E[Y] + E[Z]}{3}\]

(b) \(E[\sqrt{XY}] = \sqrt{E[X]\,E[Y]}\) при независимых \(X\) и \(Y\):

В общем случае неверно, даже при независимости.

Контрпример: пусть \(X = Y\) — независимые копии величины, принимающей \(1\) и \(4\) с вероятностью \(\frac{1}{2}\).

Тогда \(E[X]=E[Y]=\frac{5}{2}\), \(\sqrt{E[X]E[Y]}=\frac{5}{2}\), а по независимости \(E[\sqrt{XY}]=E[\sqrt{X}]E[\sqrt{Y}]=(\frac{3}{2})^2=\frac{9}{4}\neq\frac{5}{2}\).

Корректное сравнение даёт Jensen’s inequality: \(\sqrt{\cdot}\) вогнута, поэтому \(E[\sqrt{Z}] \leq \sqrt{E[Z]}\).

(c) \(E[\max(X, Y)] = \max(E[X], E[Y])\):

Неверно в общем случае. Для независимых равновероятных \(X,Y\in\{0,1\}\) получаем \(E[\max(X,Y)]=\frac{3}{4}\neq\frac{1}{2}\). Вообще \(E[\max(X,Y)] \geq \max(E[X],E[Y])\).

(d) \(E[X^3] = (E[X])^3\):

Неверно. Для \(X\in\{0,2\}\) равновероятно: \((E[X])^3=1\), \(E[X^3]=4\).

Ответ: (a) Верно по линейности. (b)–(d) Неверно — контрпримеры как выше.

4.3. Алгоритм Modular-Search (Набор задач 7, Задание 3)

Рассмотрите алгоритм Modular-Search: фиксированный шаг \(s\), старт с индекса 1, визиты \(1, 1+s, 1+2s, \ldots\) по модулю \(n\) в диапазоне \([1..n]\). При \(\gcd(n, s) = 1\) за \(n\) шагов каждый индекс ровно раз. Остановка при первом вхождении целевого \(x\). В \(A[1..n]\) ровно \(k\) копий \(x\).

(a) Опишите алгоритм и приведите псевдокод Modular-Search.

(b) Проанализируйте худший, лучший и ожидаемый случаи по времени.

(c) Псевдокод Randomized-Search (случайная перестановка индексов вместо фиксированного шага).

(d) Ожидаемое время Randomized-Search.

(e) Сравните алгоритмы: когда детерминированный медленен и чем помогает рандомизация.

Нажмите, чтобы увидеть решение

Ключевая идея: Modular-Search — детерминированный обход; Randomized-Search использует случайную перестановку, чтобы избежать враждебного худшего случая.

(a) Псевдокод Modular-Search:

MODULAR-SEARCH(A, n, x, s)
1  idx = 1
2  for step = 1 to n
3      if A[idx] == x
4          return idx       // found x
5      idx = (idx - 1 + s) mod n + 1   // advance by s modulo n (1-indexed)
6  return NOT_FOUND

Словесно: проверяем позиции \(1, 1+s, 1+2s, \ldots\) (по модулю \(n\), индексация с 1). При \(\gcd(n,s)=1\) за \(n\) шагов обходятся все индексы. Останавливаемся при первом \(A[idx]=x\).

(b) Время работы:

Худший случай: противник ставит все \(k\) копий \(x\) на последние \(k\) позиций в порядке Modular-Search; тогда просматриваем \(n-k+1\) позицию.

\[T_{\text{worst}} = \Theta(n - k + 1)\]

При \(k=0\) всегда \(\Theta(n)\); при константном \(k\) худший случай остаётся \(\Theta(n)\).

Лучший случай: первая посещённая ячейка содержит \(x\) — один шаг: \(T_{\text{best}}=\Theta(1)\).

Ожидаемый случай (позиции \(k\) копий \(x\) случайны): ожидаемое число шагов до первого попадания

\[E[T] = \frac{n+1}{k+1} = \Theta\!\left(\frac{n}{k}\right)\]

(c) Randomized-Search:

RANDOMIZED-SEARCH(A, n, x)
1  pi = RANDOMLY-PERMUTE([1..n])   // generate a random permutation of indices
2  for i = 1 to n
3      if A[pi[i]] == x
4          return pi[i]            // found x
5  return NOT_FOUND

(d) Для любого фиксированного массива с \(k\) копиями \(x\) перестановка \(\pi\) даёт ожидаемую позицию первого вхождения \(\frac{n+1}{k+1}=\Theta(n/k)\); случайность в перестановке, не во входе.

(e) Modular-Search медлен, если противник знает \(s\) и расставляет копии в конец модульного порядка — \(\Theta(n)\) независимо от \(k\). Randomized-Search каждый запуск использует новую перестановку; ожидаемое время \(\Theta(n/k)\) на любом фиксированном входе.

Ответ: Modular-Search — худший \(\Theta(n)\) (контролируется противником); Randomized-Search — ожидаемое \(\Theta(n/k)\).

4.4. Равномерно ли распределение? (Лекция 7, Пример 1)

Равномерно ли распределение в случаях:

(a) честный шестигранный кубик;

(b) сумма двух честных кубиков;

(c) случайный студенческий ID в группе из \(n\) человек.

Нажмите, чтобы увидеть решение

(a) Да — равномерно на \(\{1,\ldots,6\}\).

(b) Нет — суммы не равновероятны на \(\{2,\ldots,12\}\).

(c) Да по умолчанию (равновероятный выбор из \(n\) ID).

4.5. Зависимые случайные величины (Лекция 7, Пример 2)

Приведите пример двух ненезависимых случайных величин.

Нажмите, чтобы увидеть решение

На одном броске: \(X = I\{\text{heads}\}\), \(Y = I\{\text{tails}\}\) — dependent: совместная вероятность \((1,1)\) равна 0, произведение маргиналей — нет.

4.6. Ожидаемое число орлов (Лекция 7, Пример 3)

Сколько в среднем орлов при \(n\) бросках честной монеты?

Нажмите, чтобы увидеть решение

Индикаторы на каждый бросок и linearity of expectation дают \(\frac{n}{2}\).

4.7. Вероятностный анализ задачи о найме (Лекция 7, Пример 4)

Ожидаемое число наймов при \(n\) кандидатах в случайном порядке?

Нажмите, чтобы увидеть решение

\(E[\sum_i X_i] = H_n = \Theta(\log n)\).

4.8. Ожидаемый счёт в игре с монетами (Лекция 7, Задание 1)

Две монеты: за каждый орёл +3, за каждую решку −2. Ожидаемый счёт?

Нажмите, чтобы увидеть решение

Ключевая идея: задать случайную величину на пространстве исходов и посчитать \(E[X]=\sum_x x\cdot\Pr\{X=x\}\).

Пусть \(S=\{HH,HT,TH,TT\}\) с вероятностью \(\tfrac14\) каждого исхода; \(X(HH)=6\), \(X(HT)=X(TH)=1\), \(X(TT)=-4\). Тогда \[E[X]=6\cdot\tfrac14+1\cdot\tfrac14+1\cdot\tfrac14+(-4)\cdot\tfrac14=1.\]

Ответ: ожидаемый счёт равен \(1\).

4.9. Ожидаемая высота случайно выбранного BST (Лекция 7, Задание 2)

(a) 5 узлов. (b) общий вид для \(n\).

Нажмите, чтобы увидеть решение

Randomly chosen BST: равномерно по \(C_n\) формам; для \(n=5\): \(C_5=42\), ожидаемая высота \(\approx 2.7\); асимптотика высоты случайного бинарного плоского дерева — \(\Theta(\sqrt{n})\), что хуже \(\Theta(\log n)\) у randomly built BST.

4.10. Ожидаемая высота случайно построенного BST (Лекция 7, Задание 3)

(a) 5 ключей. (b) для \(n\).

Нажмите, чтобы увидеть решение

Randomly built BST: случайная перестановка вставок; для \(n=5\) ожидаемая высота \(\approx 2.8\); для общего \(n\) — \(\Theta(\log n)\) (Cormen et al. 2022, §12.4).